package com.now.doublepointer;

import java.util.Arrays;

/**
 * 977. 有序数组的平方
 * 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
 */
public class SortedSquares {
    /**
     * 两次循环，耗时
     * @param nums
     * @return
     */
    public static int[] sortedSquares(int[] nums) {
        int[] result= new int[nums.length];
        int m;
        for(int i=0;i<=nums.length-1;i++){
            for(int j=i+1;j<=nums.length-1;j++){
                if(nums[i]*nums[i]>nums[j]*nums[j]){
                    m=nums[j];
                    nums[j]=nums[i];
                    nums[i]=m;
                }
            }
            result[i]=nums[i]*nums[i];
        }
        return result;
    }

    /**
     * 使用类库，多次循环嵌套多层循环费时
     * @param nums
     * @return
     */
    public static int[] sortedSquares2(int[] nums) {
        int[] ans = new int[nums.length];
        for (int i = 0; i < nums.length; ++i) {
            ans[i] = nums[i] * nums[i];
        }
        Arrays.sort(ans);
        return ans;
    }

    /**
     * 双指针，找到中间正负交界点，平方后的结果，交接点左边是递减，交接后右边是递增
     * 从交界左右两边比较，循环次数少
     * @param nums
     * @return
     */
    public static int[] sortedSquares3(int[] nums) {
        int regist=0;
        for(int i=0;i<nums.length;i++){
            if(nums[i]<0){
                regist=i;
            }else{
                break;
            }
        }
        int index=0,left = regist,right = regist+1;
        int[] ans = new int[nums.length];
        while(left>=0||right<=nums.length-1){
            if(left<0){
                ans[index] =nums[right]*nums[right];
                right++;
            }else if(right>nums.length-1){
                ans[index] = nums[left]*nums[left];
                left--;
            }
            else if(nums[left]*nums[left]<nums[right]*nums[right]){
                ans[index] = nums[left]*nums[left];
                left--;
            }else{
                ans[index] =nums[right]*nums[right];
                right++;
            }
            index++;
        }
        return ans;
    }
    /**
     * 使用两个指针分别指向位置 00 和 n-1n−1，每次比较两个指针对应的数，选择较大的那个逆序放入答案并移动指针。
     * 这种方法无需处理某一指针移动至边界的情况
     * @param nums
     * @return
     */
    public static int[] sortedSquares4(int[] nums) {
        int[] ans = new int[nums.length];
        int i=0,j=nums.length-1;
        int index = j;
        while(i<=j){
            if(nums[i]*nums[i]<nums[j]*nums[j]){
                ans[index] = nums[j]*nums[j];
                j--;
            }else{
                ans[index] =nums[i]*nums[i];
                i++;
            }
            index--;
        }
        return ans;
    }

    /**
     *
     * @param args
     */
    public static void main(String[] args) {
        int[] nums = {-4,-1,0,3,10};
        System.out.println(sortedSquares4(nums));
    }
}
